Computers typically execute programs in one or more processes or threads (generally “processes”) on one or more processors. If a program comprises a number of cooperating processes which can be processed in parallel on a plurality of processors, problems arise in connection with scheduling execution of the processes so that the programs can be executed in an efficient manner. Typically, operating systems have scheduled processes without regard to whether they comprise part of a parallel program, which can lead to severe inefficiencies in execution. For example, if one process in a parallel program is waiting for data that is to be provided by another process in the parallel program, or perhaps from another program, if the operating system enables the waiting process to be executed before the process which is to supply the data has provided the data, the time during which the waiting process is executed will be wasted. The problem is exacerbated when the computer is processing several such parallel programs contemporaneously, and the total number of processes of all parallel programs is greater than the number of processors in the computer available for executing those processes.
Several methodologies have been developed for scheduling execution of processes comprising one or more parallel programs. In one methodology, referred to as “batch-queuing,” the computer executes processes of only one parallel program at a time, and executes those processes until all are completed. However, batch-queuing generally precludes sharing of the computer in an interactive manner.
In another methodology, referred to as “gang scheduling,” the computer also executes processes of only one parallel program at a time, but allows for interactivity. In a computer which implements the gang scheduling methodology, a master entity, forming, for example, part of the operating system, periodically determines which parallel program to schedule at any point in time. Preferably, the master entity will make such determinations at frequent, regular intervals. At the beginning of each interval, the master entity selects which parallel program is to be processed during the interval, and allow all of the processes of only the selected program to be executed during the interval. At the end of the interval, the master entity will stop execution of that program and select another program to be executed. This methodology allows for interactivity with the various programs being executed, but the master entity adds a not-inconsiderable amount of processing overhead. The overhead can be reduced by making the intervals longer. However, if the intervals are made longer, the interactivity response time can be relatively poor. In addition, with this methodology it is not possible to process two parallel programs that communicate with each other since they will never be scheduled for execution at the same time.
In a third methodology, referred to as “co-scheduling,” each process, while it is being executed, determines for itself whether it is to be scheduled for execution, or to de-schedule itself. The processes can make the determination based on a number of factors, such as, for example, its communication patterns, responsiveness of other processes to requests, whether it is waiting for information from another process, and the like. For example, if a process determines that it has been waiting too long for information from another process, it (that is, the waiting process) can de-schedule itself, so that it will not be executed. This allows execution of other processes, which are not similarly waiting for information and which therefore can make progress in their processing operations. Since each process determines whether it is to be scheduled, no master entity is required to make such scheduling decisions. In addition, since a computer can be executing the processes comprising multiple programs, the methodology allows for a high degree of interactivity and execution of multiple parallel programs that communicate with each other.